package hot150;

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Random;

// https://leetcode.cn/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150
public class q12 {

    /**
     * 模拟
     * 24 ms
     */

    // 存储值和索引
    public HashMap<Integer, Integer> map;

    // 存储值
    public int[]nums;

    // 数组长度
    public int length;

    // 随机数
    Random random = new Random();

    public RandomizedSet() {
        // 初始化
        map = new HashMap<>();
        nums = new int[2 * (int)1e5 + 1];
        length = 0;
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        // 记录下标和值关系
        map.put(val, length + 1);
        nums[length++] = val;
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        nums[map.get(val)] = nums[--length];
        // 如果相同则不更新，不相同则更新新值到删除的索引上
        if (map.get(val) !=  length) {
            map.put(nums[map.get(val)], map.get(val));
        }
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return nums[random.nextInt(length)];
    }

}
